n=2000;
roads=[|2,1|
3,1|
4,1|
5,1|
6,1|
1,7|
1,8|
1,9|
1,10|
1,11|
12,1|
13,1|
1,14|
15,1|
1,16|
1,17|
1,18|
1,19|
1,20|
21,1|
1,22|
1,23|
24,1|
1,25|
26,1|
27,1|
28,1|
29,1|
1,30|
31,1|
32,1|
33,13|
1,34|
35,1|
36,1|
37,1|
38,1|
39,1|
1,40|
41,1|
42,1|
43,1|
1,44|
45,1|
1,46|
1,47|
48,1|
49,1|
1,50|
1,51|
1,52|
53,1|
1,54|
55,1|
56,54|
1,57|
58,1|
59,1|
1,60|
1,61|
1,62|
1,63|
1,64|
65,1|
66,1|
1,67|
1,68|
69,1|
70,1|
1,71|
72,1|
73,1|
1,74|
60,75|
76,1|
77,1|
1,78|
1,79|
80,37|
81,80|
1,82|
1,83|
1,84|
1,85|
1,86|
87,52|
1,88|
89,1|
1,90|
1,91|
1,92|
93,1|
1,94|
1,95|
1,96|
97,1|
98,1|
1,99|
1,100|
101,1|
102,1|
1,103|
1,104|
1,105|
1,106|
1,107|
1,108|
109,1|
1,110|
111,1|
112,1|
113,1|
114,1|
1,115|
116,52|
1,117|
118,1|
1,119|
1,120|
1,121|
1,122|
1,123|
124,1|
1,125|
1,126|
1,127|
1,128|
129,1|
1,130|
131,1|
132,1|
1,133|
134,1|
135,1|
136,1|
1,137|
1,138|
1,139|
140,1|
117,141|
1,142|
143,1|
144,1|
1,145|
108,146|
123,147|
148,1|
149,1|
1,150|
151,1|
1,152|
153,1|
51,154|
155,1|
156,1|
34,157|
158,1|
1,159|
160,1|
1,161|
162,1|
163,45|
1,164|
1,165|
1,166|
167,1|
1,168|
1,169|
170,1|
29,171|
172,1|
1,173|
174,1|
1,175|
176,1|
177,1|
1,178|
1,179|
139,180|
1,181|
182,1|
183,1|
1,184|
1,185|
186,1|
1,187|
188,1|
189,36|
1,190|
191,1|
192,1|
193,1|
1,194|
195,1|
196,1|
197,1|
1,198|
199,1|
1,200|
1,201|
202,1|
203,1|
204,1|
1,205|
1,206|
207,1|
208,1|
209,1|
1,210|
1,211|
212,1|
213,1|
214,1|
1,215|
216,1|
1,217|
218,1|
219,1|
220,1|
221,1|
1,222|
223,188|
224,1|
225,1|
226,1|
1,227|
228,1|
229,1|
1,230|
1,231|
1,232|
233,226|
234,1|
1,235|
1,236|
1,237|
1,238|
1,239|
240,1|
1,241|
1,242|
1,243|
244,1|
1,245|
1,246|
247,1|
1,248|
1,249|
1,250|
251,1|
222,252|
253,1|
1,254|
255,1|
256,1|
1,257|
258,1|
1,259|
1,260|
261,1|
1,262|
263,1|
1,264|
1,265|
1,266|
267,1|
1,268|
1,269|
270,1|
271,1|
1,272|
273,1|
274,1|
1,275|
1,276|
277,1|
1,278|
279,1|
280,1|
281,235|
171,282|
283,1|
284,21|
285,1|
1,286|
1,287|
288,1|
289,1|
290,75|
291,1|
1,292|
293,1|
294,1|
295,72|
1,296|
297,230|
1,298|
299,24|
300,1|
301,279|
302,1|
303,23|
304,1|
1,305|
306,1|
1,307|
308,1|
1,309|
1,310|
1,311|
312,1|
313,1|
1,314|
1,315|
316,1|
1,317|
1,318|
319,197|
320,1|
321,1|
1,322|
323,1|
324,1|
1,325|
1,326|
327,1|
328,138|
1,329|
330,187|
1,331|
332,1|
333,1|
1,334|
335,1|
336,1|
1,337|
338,1|
1,339|
1,340|
1,341|
342,1|
343,1|
1,344|
1,345|
1,346|
347,102|
348,1|
1,349|
1,350|
351,227|
352,1|
182,353|
1,354|
355,1|
356,1|
357,1|
358,235|
1,359|
360,1|
361,1|
362,1|
1,363|
364,1|
365,1|
366,1|
1,367|
1,368|
369,1|
1,370|
1,371|
1,372|
1,373|
1,374|
375,1|
170,376|
1,377|
378,1|
1,379|
1,380|
1,381|
382,1|
1,383|
1,384|
1,385|
386,1|
387,1|
388,1|
389,1|
1,390|
1,391|
1,392|
1,393|
1,394|
395,1|
396,1|
228,397|
1,398|
399,1|
400,1|
401,1|
1,402|
403,1|
1,404|
146,405|
1,406|
407,1|
1,408|
1,409|
1,410|
411,1|
359,412|
413,1|
1,414|
415,1|
1,416|
1,417|
1,418|
419,1|
1,420|
421,162|
422,1|
423,326|
1,424|
425,1|
80,426|
427,1|
1,428|
429,1|
1,430|
1,431|
432,1|
433,1|
434,1|
1,435|
436,1|
1,437|
438,1|
1,439|
440,1|
1,441|
1,442|
443,1|
444,1|
1,445|
446,1|
1,447|
1,448|
449,1|
1,450|
451,1|
1,452|
1,453|
454,1|
455,1|
456,1|
457,1|
1,458|
1,459|
460,1|
1,461|
462,1|
463,1|
1,464|
465,1|
1,466|
467,1|
256,468|
1,469|
1,470|
1,471|
472,1|
473,1|
474,1|
1,475|
476,318|
477,1|
1,478|
479,1|
480,1|
481,1|
482,1|
1,483|
1,484|
1,485|
1,486|
487,37|
488,1|
489,1|
490,1|
491,1|
492,1|
1,493|
230,494|
1,495|
1,496|
497,1|
498,1|
1,499|
1,500|
1,501|
502,1|
1,503|
504,1|
1,505|
1,506|
507,1|
1,508|
509,1|
510,372|
511,1|
512,1|
1,513|
1,514|
1,515|
516,1|
517,1|
518,1|
519,1|
520,1|
1,521|
1,522|
1,523|
524,1|
1,525|
526,1|
527,1|
1,528|
529,1|
1,530|
531,1|
532,1|
533,1|
534,1|
1,535|
536,1|
1,537|
1,538|
539,1|
1,540|
541,1|
131,542|
460,543|
1,544|
1,545|
1,546|
1,547|
1,548|
1,549|
550,1|
551,1|
552,1|
553,1|
1,554|
1,555|
556,498|
1,557|
1,558|
559,1|
1,560|
1,561|
562,1|
1,563|
564,1|
565,1|
296,566|
567,305|
568,1|
1,569|
570,1|
571,1|
1,572|
1,573|
1,574|
1,575|
576,1|
577,1|
578,1|
1,579|
580,1|
581,557|
582,259|
583,1|
1,584|
585,1|
1,586|
587,1|
588,1|
1,589|
590,1|
1,591|
1,592|
593,1|
513,594|
1,595|
596,1|
1,597|
598,1|
1,599|
1,600|
601,1|
602,1|
603,1|
604,1|
605,1|
606,1|
126,607|
608,478|
1,609|
610,1|
1,611|
612,1|
613,1|
614,1|
615,1|
616,1|
617,1|
618,1|
236,619|
1,620|
621,1|
1,622|
623,1|
624,1|
1,625|
1,626|
627,41|
628,1|
629,1|
1,630|
631,1|
632,1|
1,633|
1,634|
635,1|
1,636|
637,1|
638,1|
1,639|
1,640|
1,641|
642,1|
1,643|
1,644|
645,1|
646,1|
647,1|
648,1|
1,649|
650,1|
1,651|
652,1|
653,1|
654,1|
655,1|
1,656|
657,1|
658,190|
659,1|
1,660|
1,661|
662,1|
663,1|
664,1|
1,665|
1,666|
667,1|
1,668|
1,669|
670,1|
671,1|
672,1|
673,1|
1,674|
627,675|
1,676|
293,677|
678,162|
670,679|
680,1|
681,1|
682,1|
683,1|
1,684|
1,685|
686,1|
687,1|
688,1|
1,689|
403,690|
691,1|
692,1|
1,693|
694,1|
1,695|
1,696|
697,1|
698,1|
1,699|
1,700|
1,701|
1,702|
703,437|
1,704|
705,1|
1,706|
1,707|
708,1|
1,709|
1,710|
711,1|
712,1|
1,713|
1,714|
1,715|
1,716|
717,1|
1,718|
719,1|
720,1|
721,1|
722,1|
1,723|
724,1|
1,725|
726,1|
1,727|
1,728|
1,729|
1,730|
1,731|
732,1|
733,1|
734,1|
735,1|
736,1|
737,1|
1,738|
1,739|
740,1|
741,1|
1,742|
743,1|
744,1|
745,1|
746,1|
747,1|
748,1|
749,1|
750,1|
1,751|
752,1|
753,1|
754,1|
583,755|
756,1|
1,757|
758,1|
1,759|
760,1|
1,761|
762,1|
763,1|
1,764|
42,765|
1,766|
698,767|
768,1|
1,769|
770,1|
1,771|
772,1|
1,773|
1,774|
775,1|
776,412|
777,1|
778,1|
779,1|
1,780|
781,1|
1,782|
1,783|
784,1|
785,1|
786,1|
1,787|
1,788|
1,789|
790,1|
1,791|
792,791|
793,791|
360,794|
791,795|
791,796|
797,132|
791,798|
799,791|
800,791|
791,801|
570,802|
803,167|
804,791|
791,805|
791,806|
807,791|
791,808|
791,809|
810,791|
811,791|
812,791|
813,791|
791,814|
815,791|
816,791|
791,817|
791,818|
819,791|
820,791|
791,821|
822,791|
823,791|
824,791|
825,791|
791,826|
827,791|
544,828|
829,791|
830,56|
831,791|
791,832|
791,833|
791,834|
488,835|
791,836|
791,837|
838,791|
839,791|
791,840|
791,841|
791,842|
843,791|
543,844|
803,845|
846,791|
791,847|
791,848|
791,849|
791,850|
851,791|
852,791|
853,791|
854,791|
855,791|
370,856|
857,791|
858,791|
791,859|
860,791|
791,861|
862,86|
791,863|
791,864|
791,865|
866,815|
867,791|
791,868|
791,869|
870,756|
871,83|
872,791|
791,873|
874,791|
875,791|
876,791|
877,329|
791,878|
791,879|
880,791|
791,881|
791,882|
883,730|
791,884|
791,885|
886,791|
887,791|
888,791|
889,791|
791,890|
891,791|
791,892|
893,791|
894,791|
791,895|
854,896|
791,897|
791,898|
899,791|
791,900|
901,791|
902,791|
570,903|
904,791|
791,905|
906,791|
791,907|
791,908|
791,909|
910,791|
911,791|
791,912|
791,913|
914,791|
791,915|
791,916|
917,791|
918,791|
791,919|
920,791|
921,453|
922,791|
923,791|
924,791|
925,791|
791,926|
791,927|
186,928|
929,791|
930,791|
931,791|
791,932|
933,100|
934,791|
791,935|
791,936|
937,791|
791,938|
791,939|
940,791|
791,941|
791,942|
943,791|
944,137|
294,945|
791,946|
947,791|
496,948|
949,791|
950,791|
791,951|
791,952|
953,791|
954,28|
955,791|
791,956|
957,791|
958,791|
959,791|
791,960|
961,791|
791,962|
791,963|
791,964|
791,965|
966,791|
791,967|
791,968|
969,791|
970,791|
971,791|
791,972|
973,791|
974,640|
975,791|
791,976|
977,791|
791,978|
791,979|
980,791|
791,981|
982,791|
983,791|
377,984|
985,791|
986,791|
791,987|
791,988|
989,791|
990,791|
991,791|
992,791|
791,993|
994,791|
791,995|
996,791|
997,791|
221,998|
999,791|
1000,791|
791,1001|
1002,791|
1003,791|
904,1004|
1005,791|
791,1006|
1007,791|
791,1008|
791,1009|
1010,791|
1011,791|
1012,791|
1013,791|
791,1014|
1015,704|
1016,791|
791,1017|
1018,823|
1019,791|
1020,791|
791,1021|
172,1022|
791,1023|
1024,791|
1025,791|
1026,791|
1027,547|
1028,439|
1029,791|
791,1030|
791,1031|
791,1032|
791,1033|
1034,791|
791,1035|
791,1036|
470,1037|
1038,791|
1039,791|
791,1040|
791,1041|
1042,791|
1043,791|
791,1044|
1045,791|
791,1046|
1047,791|
1048,791|
791,1049|
791,1050|
1051,571|
1052,791|
791,1053|
791,1054|
791,1055|
1056,791|
791,1057|
1058,630|
791,1059|
1060,791|
1061,791|
791,1062|
1063,791|
1064,791|
1065,813|
791,1066|
1067,791|
1068,791|
791,1069|
791,1070|
791,1071|
1072,791|
1073,791|
791,1074|
1075,791|
1076,791|
1077,791|
1078,791|
791,1079|
791,1080|
1081,791|
1082,791|
791,1083|
1084,791|
791,1085|
1086,791|
791,1087|
791,1088|
791,1089|
1090,791|
1091,791|
1092,791|
791,1093|
791,1094|
1095,791|
791,1096|
1097,791|
1098,791|
791,1099|
791,1100|
791,1101|
791,1102|
1103,791|
1104,791|
791,1105|
1106,791|
1107,791|
1108,791|
1109,791|
1110,791|
791,1111|
791,1112|
791,1113|
1114,946|
791,1115|
791,1116|
1117,260|
1118,791|
1119,791|
1120,791|
1121,791|
1122,791|
791,1123|
1124,791|
791,1125|
791,1126|
858,1127|
1128,494|
1129,791|
1130,791|
316,1131|
1132,791|
1133,791|
791,1134|
791,1135|
1136,1104|
1137,791|
791,1138|
791,1139|
791,1140|
1141,791|
791,1142|
1143,791|
791,1144|
1145,791|
791,1146|
1147,791|
1148,791|
1149,791|
791,1150|
1151,791|
791,1152|
791,1153|
791,1154|
1155,791|
791,1156|
791,1157|
1158,791|
791,1159|
791,1160|
791,1161|
1162,791|
1163,791|
791,1164|
791,1165|
791,1166|
1167,791|
1168,791|
1169,791|
791,1170|
1171,791|
1172,791|
28,1173|
791,1174|
791,1175|
1176,791|
1177,791|
695,1178|
1179,791|
1180,791|
1181,791|
791,1182|
1183,791|
1184,791|
791,1185|
1186,791|
791,1187|
507,1188|
1189,791|
791,1190|
791,1191|
1192,791|
791,1193|
1194,791|
791,1195|
1196,411|
791,1197|
1198,791|
705,1199|
1200,1162|
1201,791|
791,1202|
791,1203|
791,1204|
791,1205|
1206,791|
1207,791|
791,1208|
791,1209|
1210,791|
791,1211|
1212,370|
791,1213|
1214,791|
1215,328|
1216,791|
791,1217|
791,1218|
791,1219|
1220,791|
1221,791|
791,1222|
1223,791|
791,1224|
791,1225|
1226,791|
791,1227|
1228,791|
1229,791|
1230,791|
791,1231|
791,1232|
1233,791|
1234,791|
791,1235|
791,1236|
1237,791|
1238,791|
1239,1013|
1240,791|
791,1241|
1242,791|
791,1243|
791,1244|
1245,791|
791,1246|
791,1247|
791,1248|
791,1249|
1250,776|
1251,302|
791,1252|
1253,791|
791,1254|
1255,791|
791,1256|
700,1257|
1258,791|
1259,791|
1260,791|
1261,791|
791,1262|
1263,791|
791,1264|
791,1265|
791,1266|
791,1267|
791,1268|
791,1269|
791,1270|
791,1271|
791,1272|
505,1273|
791,1274|
791,1275|
791,1276|
1277,791|
1278,791|
1279,791|
1280,791|
1281,791|
791,1282|
1283,791|
791,1284|
791,1285|
1286,1269|
1287,791|
791,1288|
791,1289|
1290,791|
791,1291|
1292,791|
1293,791|
1294,791|
1295,791|
1296,791|
1297,791|
1298,791|
791,1299|
1300,791|
791,1301|
1302,1192|
791,1303|
1304,791|
791,1305|
1306,791|
1307,791|
1308,791|
1309,791|
791,1310|
1311,791|
791,1312|
791,1313|
1314,791|
1315,742|
791,1316|
791,1317|
1318,1143|
1319,791|
791,1320|
791,1321|
791,1322|
1323,791|
791,1324|
791,1325|
1326,791|
1327,791|
1328,791|
1329,791|
1186,1330|
1331,791|
791,1332|
791,1333|
791,1334|
791,1335|
1336,791|
791,1337|
791,1338|
791,1339|
1340,791|
1341,791|
1342,791|
1343,791|
1344,791|
791,1345|
791,1346|
791,1347|
1348,791|
1349,791|
791,1350|
1351,791|
1352,1318|
1353,791|
1354,791|
791,1355|
791,1356|
1357,188|
1358,791|
791,1359|
791,1360|
791,1361|
791,1362|
1363,791|
791,1364|
393,1365|
1366,791|
384,1367|
1368,791|
1369,791|
1370,791|
986,1371|
1372,791|
1373,999|
791,1374|
791,1375|
1376,74|
1377,791|
1378,791|
791,1379|
1380,791|
1381,791|
791,1382|
1383,791|
791,1384|
1385,791|
791,1386|
1387,791|
1388,791|
791,1389|
791,1390|
791,1391|
791,1392|
791,1393|
1394,791|
1395,791|
791,1396|
1397,791|
1398,791|
1399,791|
1400,791|
1401,791|
1313,1402|
1403,1392|
791,1404|
791,1405|
1406,791|
485,1407|
791,1408|
791,1409|
791,1410|
791,1411|
1412,791|
1413,791|
1414,791|
1415,791|
791,1416|
1417,791|
1418,804|
1419,791|
791,1420|
791,1421|
585,1422|
1423,524|
791,1424|
1425,791|
1426,791|
949,1427|
1428,791|
791,1429|
1430,791|
1431,791|
791,1432|
791,1433|
791,1434|
1435,791|
791,1436|
791,1437|
791,1438|
791,1439|
791,1440|
1440,1441|
1440,1442|
1443,1440|
111,1444|
1440,1445|
1446,1440|
1447,6|
1440,1448|
1449,1104|
1440,1450|
1451,1440|
1452,1440|
1453,1440|
1440,1454|
1455,1454|
1456,1454|
1457,1454|
1454,1458|
1454,1459|
1454,1460|
1461,909|
1462,1454|
1454,1463|
1464,1454|
1454,1465|
1454,1466|
1467,1454|
1468,1454|
1454,1469|
1470,1454|
1471,1454|
1472,1454|
1048,1473|
1474,1454|
1454,1475|
1476,1454|
1477,1454|
1478,1454|
1479,1454|
1454,1480|
1454,1481|
1294,1482|
1454,1483|
1454,1484|
1454,1485|
1486,1454|
1487,1454|
1488,1454|
1454,1489|
1490,1454|
1454,1491|
1492,710|
1493,1454|
1454,1494|
1495,1454|
1496,1454|
1454,1497|
1498,1454|
1454,1499|
1454,1500|
1454,1501|
1454,1502|
1503,779|
1504,1454|
1454,1505|
1454,1506|
1454,1507|
1454,1508|
1454,1509|
1395,1510|
1511,1454|
1512,624|
1454,1513|
1454,1514|
1515,1454|
1516,1454|
1454,1517|
1454,1518|
1454,1519|
1520,1454|
1521,1454|
1454,1522|
1523,1454|
1524,1454|
1454,1525|
1526,1418|
1527,1454|
1454,1528|
1454,1529|
1530,1454|
1531,1454|
1532,1454|
1454,1533|
1454,1534|
1454,1535|
1454,1536|
1537,448|
1538,1454|
1454,1539|
447,1540|
1454,1541|
1454,1542|
1543,1454|
1544,1454|
1545,1454|
1454,1546|
1547,1454|
1454,1548|
1549,1454|
1550,1454|
1551,1454|
1552,1454|
1454,1553|
1554,1454|
1555,1454|
1556,343|
1557,1454|
1454,1558|
1559,1454|
1560,1454|
1454,1561|
1562,926|
1563,1454|
1454,1564|
1565,1454|
1454,1566|
1454,1567|
619,1568|
1454,1569|
1570,1454|
1454,1571|
1454,1572|
1573,1454|
1454,1574|
1454,1575|
1576,1454|
1577,1454|
1578,1454|
1579,1454|
1580,1454|
1454,1581|
1582,769|
1454,1583|
1584,1454|
1585,779|
1454,1586|
1454,1587|
1588,386|
549,1589|
1590,1454|
1591,1454|
1592,557|
1593,1454|
1454,1594|
1595,1454|
1596,1454|
1454,1597|
1598,1454|
1454,1599|
1600,1454|
1601,1454|
1454,1602|
1603,1454|
1604,1454|
758,1605|
1606,1454|
1454,1607|
1454,1608|
1609,442|
1610,1454|
1611,1454|
1612,1454|
1454,1613|
1614,775|
1615,1454|
1616,1454|
1617,1454|
1618,1454|
1619,1454|
1454,1620|
1621,1454|
1454,1622|
190,1623|
1624,1284|
1454,1625|
1626,1454|
1454,1627|
1628,1454|
1629,1454|
1630,1454|
1454,1631|
1454,1632|
1454,1633|
1454,1634|
1454,1635|
1636,1454|
1637,1454|
1638,1454|
1639,1454|
1454,1640|
1454,1641|
1454,1642|
1643,1454|
1644,1454|
1454,1645|
1646,1454|
39,1647|
1454,1648|
1649,1454|
1454,1650|
1651,1454|
1454,1652|
1653,1454|
1454,1654|
1454,1655|
1656,1454|
1454,1657|
1454,1658|
1659,1454|
1454,1660|
1454,1661|
1307,1662|
1663,1454|
1454,1664|
1665,1454|
1666,1454|
1454,1667|
1668,1454|
1669,1454|
1670,444|
1454,1671|
1454,1672|
1454,1673|
1454,1674|
1675,1454|
1676,1454|
1454,1677|
1678,1454|
1454,1679|
1680,303|
1681,1454|
1454,1682|
1454,1683|
1454,1684|
1454,1685|
1686,1454|
1687,1454|
1688,1454|
1689,1454|
1454,1690|
1454,1691|
1692,981|
1454,1693|
1454,1694|
1454,1695|
1454,1696|
1454,1697|
1454,1698|
1454,1699|
1454,1700|
303,1701|
1702,1454|
1703,1259|
1454,1704|
1454,1705|
1454,1706|
379,1707|
1708,1454|
1454,1709|
1710,1454|
1454,1711|
1712,1454|
1713,1454|
1454,1714|
1454,1715|
1716,1454|
1717,1454|
1092,1718|
1454,1719|
1720,1454|
1454,1721|
1722,1412|
1454,1723|
1724,1454|
1454,1725|
1726,1454|
1454,1727|
1728,1454|
1729,1454|
871,1730|
1454,1731|
1454,1732|
1454,1733|
1454,1734|
1735,1454|
1736,1454|
1737,1454|
1738,1454|
7,1739|
1454,1740|
1454,1741|
1454,1742|
1743,1454|
1744,1454|
1454,1745|
1454,1746|
1454,1747|
1151,1748|
1454,1749|
1454,1750|
1751,1454|
1752,1454|
1454,1753|
1454,1754|
1755,1454|
1756,1454|
1454,1757|
1758,1454|
1759,1454|
1760,1454|
1454,1761|
1454,1762|
1454,1763|
1454,1764|
1454,1765|
1766,1454|
1767,1454|
1768,1454|
1454,1769|
1770,1454|
1771,1454|
1772,1454|
1773,799|
1454,1774|
1775,1454|
1454,1776|
1777,1454|
1778,1454|
1779,607|
1454,1780|
1781,1454|
1782,1454|
1454,1783|
1784,703|
1785,1454|
1541,1786|
1787,1454|
1454,1788|
1789,1454|
1790,1454|
1454,1791|
1454,1792|
1454,1793|
1454,1794|
1454,1795|
1796,1454|
1454,1797|
1454,1798|
1454,1799|
1800,542|
1454,1801|
1802,1454|
1803,1454|
1804,1454|
1454,1805|
1806,1454|
1454,1807|
1808,1454|
1454,1809|
1434,1810|
1811,1454|
1435,1812|
1813,1454|
1454,1814|
1815,1454|
1454,1816|
1817,1454|
1454,1818|
1454,1819|
42,1820|
1821,1454|
1454,1822|
1823,1454|
1824,1454|
1825,1454|
1454,1826|
1827,1454|
1828,1454|
1454,1829|
1830,1454|
1454,1831|
1832,1454|
1833,1454|
1440,1834|
969,1835|
1454,1836|
1837,1454|
1454,1838|
1839,1454|
1454,1840|
1841,1454|
1454,1842|
1843,1454|
1454,1844|
1454,1845|
1454,1846|
1454,1847|
1848,1454|
1454,1849|
1454,1850|
1454,1851|
1454,1852|
1454,1853|
1454,1854|
1855,1454|
1856,1454|
1454,1857|
1454,1858|
1454,1859|
1860,1454|
1454,1861|
1862,1454|
1761,1863|
1454,1864|
1454,1865|
1866,1454|
1867,835|
1868,1454|
1454,1869|
1870,1454|
55,1871|
1872,1454|
1454,1873|
1874,1454|
1875,1454|
1454,1876|
1454,1877|
1878,1454|
1454,1879|
1454,1880|
1881,1454|
1454,1882|
1454,1883|
1454,1884|
1454,1885|
1454,1886|
1454,1887|
1888,1454|
1454,1889|
1454,1890|
1454,1891|
1454,1892|
1893,1454|
1454,1894|
1454,1895|
1896,1454|
1454,1897|
1898,1454|
1454,1899|
1900,1454|
1454,1901|
1902,1454|
1903,1454|
1904,1454|
1454,1905|
1454,1906|
1907,1454|
1454,1908|
1909,1454|
1454,1910|
1911,1454|
1454,1912|
1913,1454|
1914,1454|
1454,1915|
1454,1916|
1454,1917|
1454,1918|
1919,1454|
1920,1454|
1921,1454|
1922,1454|
1923,1454|
1924,1454|
1925,1454|
1926,1454|
1454,1927|
1928,1454|
1454,1929|
1454,1930|
1931,1454|
1454,1932|
1454,1933|
1934,1454|
1935,1454|
1936,1454|
1454,1937|
1938,1454|
1454,1939|
1940,1454|
1454,1941|
1454,1942|
1943,1454|
1944,1454|
520,1945|
1946,1454|
1947,1454|
1948,1454|
1454,1949|
1950,1454|
1951,1454|
1454,1952|
1953,1454|
1954,1454|
1454,1955|
1454,1956|
1454,1957|
257,1958|
239,1959|
1960,1454|
1961,1454|
1962,1454|
1454,1963|
1964,1454|
1454,1965|
1966,1454|
1454,1967|
1454,1968|
1969,1454|
1970,1454|
1454,1971|
1972,1454|
1973,1454|
1454,1974|
1975,1454|
1976,1454|
1977,1454|
1978,1454|
1979,1454|
1454,1980|
1981,1454|
1454,1982|
1454,1983|
1454,1984|
1454,1985|
1986,1454|
1987,1454|
1988,1454|
1454,1989|
1990,928|
1991,1454|
1992,1454|
1993,1454|
1454,1994|
458,1995|
1454,1996|
1454,1997|
919,1998|
1454,1999|
1454,2000|];
W=[64,380,985,82,866,838,261,739,571,91,397,699,698,716,412,168,128,699,64,176,388,103,677,138,41,912,313,3,867,853,589,211,936,451,914,129,845,61,223,833,953,528,529,579,484,725,579,632,26,702,161,564,552,808,667,314,268,984,48,262,765,650,746,347,671,238,277,218,279,774,508,273,176,738,189,693,201,724,529,345,141,117,213,917,421,500,565,226,250,265,348,91,714,510,390,614,254,781,912,218,236,62,392,328,347,521,102,343,655,363,445,365,272,286,927,448,889,831,118,345,197,267,347,994,769,651,795,286,747,421,148,566,297,510,987,251,394,473,53,391,4,694,960,136,556,368,525,519,256,509,794,64,550,765,410,982,220,61,410,727,241,728,709,780,518,755,683,979,490,366,879,69,199,513,464,248,171,225,635,700,464,443,266,444,748,697,53,923,40,202,523,625,107,504,295,87,998,999,785,728,737,502,161,828,808,71,231,938,214,706,820,158,643,287,889,428,903,40,718,708,207,2,861,267,328,123,350,479,840,901,15,304,263,942,43,978,455,333,406,597,46,949,496,255,203,747,319,950,657,620,76,769,625,686,619,692,132,178,471,198,502,897,620,860,333,360,82,654,666,190,820,602,468,493,540,698,236,452,135,401,667,964,690,388,271,622,56,569,656,763,896,367,257,506,401,655,650,757,516,938,951,974,163,200,505,907,456,870,744,235,165,569,772,644,109,127,85,872,918,205,728,22,322,36,984,312,18,694,18,444,204,502,906,640,775,44,248,838,614,941,626,779,651,688,111,584,438,611,13,909,315,11,514,159,264,982,53,795,366,904,352,807,399,243,972,710,914,245,601,385,25,971,149,4,875,577,118,736,370,382,614,325,626,598,869,213,298,993,40,896,859,964,898,976,255,459,939,709,374,47,707,142,696,327,610,316,122,625,215,599,469,7,543,59,304,93,358,765,943,803,536,414,736,104,484,820,985,257,175,666,712,418,755,73,627,608,231,65,955,935,819,159,119,598,846,297,357,835,761,982,862,287,545,274,916,684,203,741,42,685,985,462,515,224,47,136,975,266,921,502,589,389,982,949,398,396,710,813,767,857,725,854,748,388,523,723,574,626,901,785,299,331,716,369,358,538,397,211,863,282,89,480,633,614,811,887,886,317,233,378,741,774,504,164,861,429,760,112,330,399,108,469,689,740,351,390,90,85,24,875,930,919,105,703,350,254,790,848,401,434,691,355,938,754,773,593,573,144,244,416,750,571,986,952,588,296,286,635,111,777,581,56,202,265,999,739,738,905,548,240,117,935,472,488,770,860,433,614,138,74,364,420,589,616,567,74,673,325,652,135,681,312,183,128,475,291,333,23,677,7,363,932,573,533,225,143,402,925,125,32,365,158,225,17,607,627,9,111,461,226,915,335,196,420,418,597,823,476,347,248,789,105,956,681,966,8,38,484,15,86,371,748,829,113,298,290,844,769,109,291,215,184,581,368,664,557,503,55,591,455,422,767,894,715,909,324,347,324,28,497,754,785,991,427,101,436,928,559,609,210,814,792,320,107,422,741,113,597,527,729,703,369,426,342,215,140,876,378,407,154,535,258,73,889,21,792,781,690,967,658,386,233,708,164,413,281,479,101,396,299,268,207,674,777,501,986,766,166,336,792,94,500,107,727,593,454,216,657,527,654,183,86,805,627,118,198,245,174,827,871,871,200,267,736,42,448,224,491,994,728,224,474,409,694,474,295,264,343,59,727,724,114,662,770,107,663,278,152,699,399,948,733,697,546,52,521,543,931,910,590,83,733,527,266,152,106,981,382,922,987,671,893,396,168,473,621,38,35,677,350,62,202,680,98,121,108,449,466,600,150,93,650,401,728,255,425,962,785,98,232,567,905,626,730,148,974,645,354,924,363,130,700,570,507,170,901,28,76,572,726,933,679,236,384,232,283,220,589,116,320,656,50,217,269,734,416,928,956,477,7,25,546,240,563,682,380,897,606,871,202,319,44,204,205,855,903,918,190,629,628,748,686,230,751,848,206,335,978,58,900,111,315,190,935,164,573,183,851,328,404,935,683,731,273,194,589,849,267,503,726,349,240,109,191,56,331,572,678,238,38,50,186,489,67,702,203,233,340,332,657,912,50,835,466,237,74,361,830,335,40,882,944,729,206,433,925,402,532,854,297,969,520,892,316,820,280,985,716,661,401,981,496,898,989,190,887,877,356,882,189,327,398,402,632,801,16,953,525,734,246,886,325,216,381,383,234,523,326,539,241,333,446,545,663,427,558,894,568,475,518,244,404,914,867,930,463,490,953,429,998,28,133,758,782,499,677,382,304,920,827,588,399,210,661,220,453,758,794,52,727,562,383,631,113,702,813,123,935,712,622,535,398,496,635,190,639,649,153,988,610,669,517,144,172,754,872,321,244,952,109,565,771,947,639,839,336,386,582,849,15,483,926,45,206,1000,946,681,231,854,827,509,341,776,449,84,89,563,724,921,784,687,550,524,190,281,812,379,820,263,922,694,27,922,308,674,151,898,885,38,34,190,262,352,707,952,665,251,19,402,702,703,26,425,65,237,935,926,947,636,880,74,650,556,775,453,792,807,279,392,851,189,668,613,74,564,291,896,7,877,932,785,390,660,758,553,652,186,210,424,538,721,609,619,760,394,190,268,687,672,479,250,887,549,625,160,403,478,570,676,422,165,258,297,34,549,340,852,528,419,320,353,302,873,352,394,781,801,79,711,314,661,535,642,885,617,984,207,399,851,984,342,74,478,45,748,176,666,559,608,407,300,745,426,228,265,437,249,161,70,819,338,186,943,272,569,917,163,32,166,766,543,374,220,90,257,902,500,20,799,81,756,774,43,93,261,766,338,703,949,788,376,556,130,799,490,57,448,339,857,102,812,339,268,822,769,448,368,84,31,76,156,984,666,450,135,386,765,182,905,375,520,363,341,770,345,123,65,938,899,970,815,73,455,350,409,769,278,19,892,261,315,377,949,695,819,105,222,756,934,6,330,830,646,425,71,282,522,284,748,182,141,514,43,913,603,478,370,332,91,574,495,457,247,165,979,444,980,730,252,203,390,819,811,805,834,933,729,281,504,579,414,506,280,437,674,415,805,317,685,776,472,48,966,981,973,523,412,830,98,493,516,971,493,334,239,189,175,139,24,188,282,525,817,38,283,485,309,634,758,215,864,973,200,488,221,872,114,385,722,369,193,500,733,223,101,783,674,27,457,325,353,95,252,897,125,162,977,735,630,206,187,584,258,658,185,254,28,525,647,505,587,338,254,399,538,709,672,927,581,697,678,471,603,483,308,497,570,626,841,710,350,752,363,796,922,80,781,689,596,434,4,87,782,3,250,257,263,315,94,713,938,563,228,425,753,495,667,990,171,250,59,491,993,135,286,165,961,772,473,114,230,941,51,942,518,133,839,992,611,659,112,416,320,306,75,125,213,517,143,702,233,321,323,382,109,782,473,834,223,277,981,388,302,976,692,976,638,875,329,477,813,381,923,525,929,136,618,552,963,444,58,40,318,225,342,863,279,252,73,528,647,914,74,95,340,162,34,45,49,307,414,89,402,503,682,878,207,990,653,190,290,57,895,397,935,236,304,395,569,331,698,74,28,322,290,208,351,481,119,641,656,863,173,393,309,840,570,566,987,738,491,386,557,85,367,445,22,46,206,685,919,560,973,867,922,705,236,889,161,214,552,424,539,856,362,285,976,454,432,134,28,157,498,516,834,464,291,220,375,852,575,418,547,709,186,170,474,775,310,115,501,700,511,256,134,318,142,442,36,53,321,833,760,405,855,396,751,637,328,152,186,726,698,129,902,607,610,720,219,436,332,38,566,753,668,728,333,219,492,742,465,315,761,246,282,825,928,896,130,391,288,301,95,32,547,851,139,989,188,761,593,708,916,39,518,742,522,214,147,921,566,826,3,414,629,303,756,957,446,864,84,633,162,765,781,655,120,197,531,856,139,769,336,991,87,581,429,127,368,752,82,695,286,436,132,641,287,571,785,492,44,659,801,320,372,717,598,675,448,538,192,979,380,230,122,622,422,606,859,915,989,295,479,744,352,803,766,820,683,215,294,319,249,72,561,311,595,547,482,863,217,832,992,238,840,617,738,951,623,255,141,514,582,592,243,944,673,169,258,136,762,590,360,945,369,403,775,520,111,875,465,394,713,280,416,600,927,428,295,120,871,2,103,145,681,592,619,942,451,99,644,446,269,956,478,742,457,868,332,781,299,187,379,484,615,264,51,800,560,277,421,197,415,833,418,947,552,63,549,866,874,939,531,694,399,299,767,66,358,130,719,217,216,241,628,514,148,714,219,36,450,310,68,837,500,683,292,821,753,57,331,780,313,28,556,453,477,580,118,326,982,611,626,720,223,972,529,503,686,317,170,329,859,77,655,56,845,97,545,379,465,510,310,90,228,666,853,77,873,601,736,258,198,256,555,557,766,312,591,326,738,671,92,692,534,463,584,740,960,486,125,683,18,184,24,474,140,960,335,174];